//此题是用队列优化了的bellmon-Ford算法，因为bellmon-Ford算法每次想要松弛更新都是对所有边进行了遍历
//但是实际上，其实有效更新只是被更新短了以后边去更新的距离
//所以每次只需要使用之前更新的过的点的距离更新其他点的距离
//而为了实现这样，就需要一个数据结构来存储之前更新过的点，这里决定用队列
//优化后的时间复杂度最好是O(m),既对于稀疏图效果最好
#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
const int INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx = 0; //因为一般用于稀疏图，所以用领接表
PII q[N];
int l = 0, r = -1; //用来优化的队列
bool st[N];        //用来记录是否入队
int dist[N];       //存储最短路长度
int n, m, a, b, c; //获取输入

void add(int a, int b, int c) //领接表里面添加边
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
    return;
}

int spfa(int x = 1, int y = n)
{
    dist[1] = 0;                            //我到我自己的距离为0
    q[++r] = PII(1, dist[1]), st[1] = true; //将初始化的结点入队，并且标记为已入队
    while (r >= l)                          //只要队列不为空，就一直更新(所以要是存在负权回路会是死循环)
    {
        PII p = q[l++];                        //从列表中取出
        int t = p.first;                       //此次出栈的点
        st[t] = false;                         //记录此点已经出栈
        for (int i = h[t]; i != -1; i = ne[i]) //尝试用t点的路径去更新其他点
        {
            int j = e[i];                 //本次遍历的点
            if (dist[j] > dist[t] + w[i]) //如果可以更新
            {
                dist[j] = dist[t] + w[i];                   //那么就更新
                if (!st[j])                                 //如果j不在队列里面，就加入队列
                    q[++r] = PII(j, dist[j]), st[j] = true; //就把j加入队列，并且标记为入队
            }
        }
    }
    if (dist[y] == INF) //这里因为只有更新后的点会用来去更新其他的点，所以可以直接用INF表示不可达
        return -1;
    else
        return dist[y];
}

int main()
{
    memset(h, -1, sizeof h);         //初始化领接表
    memset(dist, 0x3f, sizeof dist); //初始化最短路径
    memset(st, false, sizeof st);    //初始化入队状况
    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if (t == -1)
        cout << "impossible";
    else
        cout << t;
    return 0;
}